{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum of 3 Non-Overlapping Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumOfThreeSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三个无重叠子数组的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，找出三个长度为 <code>k</code> 、互不重叠、且全部数字和（<code>3 * k</code> 项）最大的子数组，并返回这三个子数组。</p>\n",
    "\n",
    "<p>以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 <strong>0</strong> 开始）。如果有多个结果，返回字典序最小的一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,1,2,6,7,5,1], k = 2\n",
    "<strong>输出：</strong>[0,3,5]\n",
    "<strong>解释：</strong>子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。\n",
    "也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,1,2,1,2,1,2,1], k = 2\n",
    "<strong>输出：</strong>[0,2,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;&nbsp;2<sup>16</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= floor(nums.length / 3)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-of-3-non-overlapping-subarrays](https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-of-3-non-overlapping-subarrays](https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1,2,6,7,5,1]\\n2', '[1,2,1,2,1,2,1,2,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        sum1, maxSum1, maxSum1Idx = 0, 0, 0\n",
    "        sum2, maxSum12, maxSum12Idx = 0, 0, ()\n",
    "        sum3, maxTotal = 0, 0\n",
    "        for i in range(k * 2, len(nums)):\n",
    "            sum1 += nums[i - k * 2]\n",
    "            sum2 += nums[i - k]\n",
    "            sum3 += nums[i]\n",
    "            if i >= k * 3 - 1:\n",
    "                if sum1 > maxSum1:\n",
    "                    maxSum1 = sum1\n",
    "                    maxSum1Idx = i - k * 3 + 1\n",
    "                if maxSum1 + sum2 > maxSum12:\n",
    "                    maxSum12 = maxSum1 + sum2\n",
    "                    maxSum12Idx = (maxSum1Idx, i - k * 2 + 1)\n",
    "                if maxSum12 + sum3 > maxTotal:\n",
    "                    maxTotal = maxSum12 + sum3\n",
    "                    ans = [*maxSum12Idx, i - k + 1]\n",
    "                sum1 -= nums[i - k * 3 + 1]\n",
    "                sum2 -= nums[i - k * 2 + 1]\n",
    "                sum3 -= nums[i - k + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        c = sum(nums[:k-1])\n",
    "        s = [0] * n\n",
    "        for i in range(k-1, n):\n",
    "            c += nums[i]\n",
    "            s[i-k+1] = c\n",
    "            c -= nums[i-k+1]\n",
    "\n",
    "        x, y, z = [0], [0, k], [0, k, 2 * k]\n",
    "        sum_1, sum_2, sum_3 = s[0], s[0] + s[k], s[0] + s[k] + s[2 * k]\n",
    "        for i in range(2*k+1, n-k+1):\n",
    "            if sum_1 < s[i - 2 * k]:\n",
    "                sum_1 = s[i - 2 * k]\n",
    "                x[0] = i - 2 * k\n",
    "            if sum_2 < sum_1 + s[i - k]:\n",
    "                sum_2 = sum_1 + s[i - k]\n",
    "                y = [*x, i - k]\n",
    "            if sum_3 < sum_2 + s[i]:\n",
    "                sum_3 = sum_2 + s[i]\n",
    "                z = [*y, i]\n",
    "\n",
    "        return z\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        sums,prefix,suffix = [0]*n,[0]*n,[0]*n\n",
    "        sums[0] = sum([nums[i] for i in range(k)])\n",
    "        for i in range(1,n-k+1):\n",
    "            sums[i] = sums[i-1]-nums[i-1]+nums[i+k-1]\n",
    "        prefix[k-1] = 0\n",
    "        for i in range(k,n):\n",
    "            if sums[i-k+1] > sums[prefix[i-1]]:\n",
    "                prefix[i] = i-k+1\n",
    "            else:\n",
    "                prefix[i] = prefix[i-1]\n",
    "        suffix[n-k] = n-k\n",
    "        for i in range(n-k-1,-1,-1):\n",
    "            if sums[i] >= sums[suffix[i+1]]:\n",
    "                suffix[i] = i\n",
    "            else:\n",
    "                suffix[i] = suffix[i+1]\n",
    "        a,b,c = 0,0,0\n",
    "        ma = 0\n",
    "        for i in range(k,n-k*2+1):\n",
    "            if sums[prefix[i-1]] + sums[i] + sums[suffix[i+k]] > ma:\n",
    "                a,b,c = prefix[i-1],i,suffix[i+k]\n",
    "                ma = sums[prefix[i-1]] + sums[i] + sums[suffix[i+k]]\n",
    "        return [a,b,c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        l = len(nums)\n",
    "        if(3*k==l):\n",
    "            return [0,k,2*k]\n",
    "        listsum = [0] * (l-k+1)\n",
    "        listmaxpos = [0] * (l-k+1)\n",
    "        list2maxpos = [0] *(l-2*k+1)\n",
    "        ans = [0]*3\n",
    "        temp = 0\n",
    "        for i in range(k):\n",
    "            temp += nums[i]\n",
    "        listsum[0]=temp\n",
    "        for i in range(l-k):\n",
    "            temp -= nums[i]\n",
    "            temp += nums[i+k]\n",
    "            listsum[i+1] = temp\n",
    "            if(temp>listsum[listmaxpos[i]]):\n",
    "                listmaxpos[i+1] = i+1\n",
    "            else:\n",
    "                listmaxpos[i+1] = listmaxpos[i]\n",
    "        max2sum = listsum[0]+listsum[k]\n",
    "        for i in range(l-2*k):\n",
    "            temp= listsum[listmaxpos[i+1]]+listsum[i+k+1]\n",
    "            if(temp>max2sum):\n",
    "                max2sum = temp\n",
    "                list2maxpos[i+1] = i+1\n",
    "            else:\n",
    "                list2maxpos[i+1] = list2maxpos[i]\n",
    "        max3sum = listsum[0]+listsum[k]+listsum[2*k]\n",
    "        list3maxpos=0\n",
    "        for i in range(l-3*k):\n",
    "            temp= listsum[listmaxpos[list2maxpos[i+1]]]+listsum[list2maxpos[i+1]+k] +listsum[i+2*k+1]\n",
    "            if(temp>max3sum):\n",
    "                max3sum = temp\n",
    "                list3maxpos = i+1\n",
    "                \n",
    "        ans[2] = list3maxpos+2*k\n",
    "        ans[1] = list2maxpos[ans[2]-2*k]+k\n",
    "        ans[0] = listmaxpos[ans[1]-k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        def OD(test_list, k):\n",
    "            # RH: This function is used to find the best answer from the list[i] to the list[end]!\n",
    "            n = len(test_list)\n",
    "            if n < k:\n",
    "                return []\n",
    "            elif n == k:\n",
    "                return [0, sum(test_list)]\n",
    "            else:\n",
    "                answer_list = [0 for _ in range(n-k+1)]\n",
    "                best_sum = sum(test_list[-k:])\n",
    "                answer_list[-1] = [n-k, best_sum]\n",
    "                for i in range(2, n-k+2):\n",
    "                    # RH: The real idx in test_list is (-k-i+1)\n",
    "                    temp_sum = sum(test_list[(-k-i+1):(-i+1)])\n",
    "                    if temp_sum >= best_sum:\n",
    "                        answer_list[-i] = [n-k-i+1, temp_sum]\n",
    "                        best_sum = temp_sum\n",
    "                    else:\n",
    "                        answer_list[-i] = answer_list[-i+1]\n",
    "                return answer_list\n",
    "\n",
    "\n",
    "        def TD(test_list, OD_list, k):\n",
    "            # RH: This function is used to find the best answer from the list[i] to the list[end] based on the OD_list\n",
    "            n = len(test_list)\n",
    "            if n < 2 * k:\n",
    "                return []\n",
    "            elif n == 2 * k:\n",
    "                return [[0, k], sum(test_list)]\n",
    "            else:\n",
    "                answer_list = [0 for _ in range(n-2*k+1)]\n",
    "                best_sum = sum(test_list[-2*k:])\n",
    "                answer_list[-1] = [[n-2*k, n-k], best_sum]\n",
    "                for i in range(2, n-2*k+2):\n",
    "                    # RH: The real idx in test_list is (-2k-i+1) when the idx is -i in answer_list\n",
    "                    temp_sum = sum(test_list[(-2*k-i+1):(-k-i+1)]) + OD_list[n-k-i+1][1]\n",
    "                    if temp_sum >= best_sum:\n",
    "                        answer_list[-i] = [[n-2*k-i+1, OD_list[n-k-i+1][0]], temp_sum]\n",
    "                        best_sum = temp_sum\n",
    "                    else:\n",
    "                        answer_list[-i] = answer_list[-i+1]\n",
    "                return answer_list\n",
    "\n",
    "        \n",
    "        def ThD(test_list, TD_list, k):\n",
    "            # RH: This function is used to find the best answer from the the list[i] to the list[end] based on the TD_list\n",
    "            n = len(test_list)\n",
    "            if n < 3 * k:\n",
    "                return []\n",
    "            elif n == 3 * k:\n",
    "                return [[0, k, 2*k, sum(test_list)]]\n",
    "            else:\n",
    "                answer_list = [0 for _ in range(n-3*k+1)]\n",
    "                best_sum = sum(test_list[-3*k:])\n",
    "                answer_list[-1] = [[n-3*k, n-2*k, n-k], best_sum]\n",
    "                for i in range(2, n-3*k+2):\n",
    "                    # RH: The real idx in test_list is (-3k-i+1) when the idx is -i in answer_list\n",
    "                    temp_sum = sum(test_list[(-3*k-i+1): (-2*k-i+1)]) + TD_list[n-2*k-i+1][1]\n",
    "                    if temp_sum >= best_sum:\n",
    "                        answer_list[-i] = [ [n-3*k-i+1, TD_list[n-2*k-i+1][0][0], TD_list[n-2*k-i+1][0][1]], temp_sum]\n",
    "                        best_sum = temp_sum\n",
    "                    else:\n",
    "                        answer_list[-i] = answer_list[-i+1]\n",
    "                return answer_list\n",
    "        \n",
    "        OD_list = OD(nums, k)\n",
    "        print(OD_list)\n",
    "        TD_list = TD(nums, OD_list, k)\n",
    "        print(TD_list)\n",
    "        THD_list = ThD(nums, TD_list, k)\n",
    "        print(THD_list)\n",
    "        return THD_list[0][0]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        path = []\n",
    "        tem, i = 0, 0\n",
    "        while i < len(nums):\n",
    "            tem += nums[i]\n",
    "            if i >= k - 1:\n",
    "                path.append(tem)\n",
    "                tem -= nums[i - k + 1]\n",
    "            i += 1\n",
    "        \n",
    "        #前后缀之和\n",
    "        pre = [[]]*len(path)\n",
    "        pre[0] = [path[0], 0]\n",
    "        for i in range(1, len(path)):\n",
    "            if path[i] > pre[i-1][0]:\n",
    "                pre[i] = [path[i], i]\n",
    "            else:\n",
    "                pre[i] = pre[i-1]\n",
    "        \n",
    "        suf = [[]]*len(path)\n",
    "        suf[-1] = [path[-1], len(path)-1]\n",
    "        for i in range(len(path)-2, -1, -1):\n",
    "            if path[i] >= suf[i+1][0]:\n",
    "                suf[i] = [path[i], i]\n",
    "            else:\n",
    "                suf[i] = suf[i+1]\n",
    "\n",
    "        maxans = 0\n",
    "        for i in range(k, len(path)-k):\n",
    "            if path[i] + pre[i-k][0] + suf[i+k][0] <= maxans:continue\n",
    "            maxans = path[i] + pre[i-k][0] + suf[i+k][0]\n",
    "            ans = [pre[i-k][1], i, suf[i+k][1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        after = [[0,0] for _ in range(n)]\n",
    "        ksum = 0\n",
    "        for i in range(n-1,n-k-1,-1):\n",
    "            ksum += nums[i]\n",
    "        after[n-k] = [ksum,n-k]\n",
    "        for i in range(n-k-1,2*k-1,-1):\n",
    "            ksum += nums[i]-nums[i+k]\n",
    "            if ksum>=after[i+1][0]:\n",
    "                after[i] = [ksum,i]\n",
    "            else:\n",
    "                after[i] = after[i+1]\n",
    "        \n",
    "        res = [0]*3\n",
    "        ksum = 0\n",
    "        prev = [[0,0] for _ in range(n)]\n",
    "        max_sum = 0\n",
    "        for i in range(k):\n",
    "            ksum += nums[i]\n",
    "        for i in range(k,n-k+1):\n",
    "            three_sum = prev[i-k][0]+ksum+after[i][0]\n",
    "            if three_sum>max_sum:\n",
    "                max_sum = three_sum\n",
    "                res = [prev[i-k][1],i-k,after[i][1]]\n",
    "            if ksum>prev[i-1][0]:\n",
    "                prev[i] = [ksum,i-k]\n",
    "            else:\n",
    "                prev[i] = prev[i-1]\n",
    "            ksum += nums[i]-nums[i-k]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        sumK = sum(nums[:k])\n",
    "        sumK_list = [sumK]  # 以index为起始位置，长度为k的连续数组和\n",
    "        for index in range(1, len(nums)-k+1):  # O(n)\n",
    "            sumK = sumK - nums[index-1] + nums[index+k-1]\n",
    "            sumK_list.append(sumK)\n",
    "        # print(sumK_list)\n",
    "        \n",
    "        max_sum2_list = [(0, 0, 0), ] * k  # 以index为第二个数组的起始位置，两个长度为k的连续数组和\n",
    "        max_sum2 = 0\n",
    "        pre_max_sumK = 0\n",
    "        first_index = -1\n",
    "        second_index = -1\n",
    "        for tmp_second_index in range(k, len(nums)-k+1):  # O(n)\n",
    "            tmp_first_index = tmp_second_index-k\n",
    "            if sumK_list[tmp_first_index] > pre_max_sumK:\n",
    "                first_index = tmp_first_index\n",
    "                pre_max_sumK = sumK_list[tmp_first_index]\n",
    "\n",
    "            tmp_max_sum2 = sumK_list[tmp_second_index] + pre_max_sumK\n",
    "            if tmp_max_sum2 > max_sum2:\n",
    "                max_sum2 = tmp_max_sum2\n",
    "                second_index = tmp_second_index\n",
    "                max_sum2_list.append((max_sum2, first_index, second_index))\n",
    "            else:\n",
    "                max_sum2_list.append(max_sum2_list[-1])\n",
    "\n",
    "        # print(max_sum2_list)\n",
    "        max_sum3 = 0\n",
    "        third_index = -1\n",
    "        for tmp_third_index in range(2*k, len(nums)-k+1):\n",
    "            tmp_sum2_index = tmp_third_index-k\n",
    "            \n",
    "            tmp_max_sum3 = max_sum2_list[tmp_sum2_index][0] + sumK_list[tmp_third_index]\n",
    "            if tmp_max_sum3 > max_sum3:\n",
    "                max_sum3 = tmp_max_sum3\n",
    "                first_index, second_index = max_sum2_list[tmp_sum2_index][1:]\n",
    "                third_index = tmp_third_index\n",
    "        \n",
    "        return [first_index, second_index, third_index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        a = [0] * (len(nums) + 1)\n",
    "        s = 0\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            a[i + 1] = s \n",
    "        for i in range(len(nums) - k + 1):\n",
    "            a[i] = a[i + k] - a[i]\n",
    "        b = [0] * (len(nums) + 1)\n",
    "        c = [0] * (len(nums) + 1)\n",
    "        m = 0\n",
    "        for i in range(len(nums) - 2 * k + 1):\n",
    "            if a[i] > a[m]:\n",
    "                m = i \n",
    "            b[i + k] = a[i + k] + a[m]\n",
    "            c[i + k] = m \n",
    "        d = [0] * len(nums)\n",
    "        e = [0] * len(nums)\n",
    "        m = k\n",
    "        for i in range(k, len(nums) - 2 * k + 1):\n",
    "            if b[i] > b[m]:\n",
    "                m = i\n",
    "            d[i + k] = a[i + k] + b[m]\n",
    "            e[i + k] = m \n",
    "        m = 2 * k\n",
    "        for i in range(2 * k, len(nums) - k + 1):\n",
    "            if d[i] > d[m]:\n",
    "                m = i \n",
    "        print(a)\n",
    "        print(b)\n",
    "        print(c)\n",
    "        print(d)\n",
    "        print(e)\n",
    "        ans = [c[e[m]], e[m], m]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        nums.reverse()\n",
    "        n = len(nums)\n",
    "        preSum = [0]\n",
    "        for num in nums:\n",
    "            preSum.append(preSum[-1] + num)\n",
    "        dp = [[0] * (3 + 1) for _ in range(n + 1)]\n",
    "        for i in range(k, n + 1):\n",
    "            for j in range(1, 4):\n",
    "                dp[i][j] = max(dp[i - 1][j], dp[i - k][j - 1] + preSum[i] - preSum[i - k])\n",
    "        res = []\n",
    "        i, j = n, 3\n",
    "        while j > 0:\n",
    "            if dp[i - 1][j] > dp[i - k][j - 1] + preSum[i] - preSum[i - k]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                res.append(n - i)\n",
    "                i -= k\n",
    "                j -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        presum = [0]+list(accumulate(nums))\n",
    "        n = len(nums)\n",
    "        goods = [presum[i+k]- presum[i] for i in range(0, n - k + 1)]\n",
    "        row = len(goods) # col = 4\n",
    "        dp = [[0]*4 for _ in range(row)]\n",
    "        for i in range(row):  #0,1,2,3.物品编号\n",
    "            for c in range(1,4):\n",
    "                if i - k < 0 and c > 1: #初始化, 注意条件,方向\n",
    "                    dp[i][c] = - inf\n",
    "                else:\n",
    "                    dp[i][c] = max(dp[i - 1][c], dp[i - k][c-1] + goods[i])\n",
    "        #还原编号\n",
    "        v = 3\n",
    "        ii = row-1\n",
    "        ans_goods = []\n",
    "        while v > 0:\n",
    "            for i in range(row):\n",
    "                if dp[i][v] == dp[ii][v]:\n",
    "                    ans_goods += i,\n",
    "                    v = v - 1\n",
    "                    ii = i - k\n",
    "                    break\n",
    "        return ans_goods[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        pre = [[] for _ in range(n)]\n",
    "        suf = [[] for _ in range(n)]\n",
    "        t = idx = 0\n",
    "        for i in range(n - k + 1):\n",
    "            if (cur := s[i + k] - s[i]) > t:\n",
    "                pre[i + k - 1] = [cur, i]\n",
    "                t, idx = pre[i + k - 1]\n",
    "            else:\n",
    "                pre[i + k - 1] = [t, idx]\n",
    "        t = idx = 0\n",
    "        for i in range(n - k, -1, -1):\n",
    "            if (cur := s[i + k] - s[i]) >= t:\n",
    "                suf[i] = [cur, i]\n",
    "                t, idx = suf[i]\n",
    "            else:\n",
    "                suf[i] = [t, idx]\n",
    "        t = 0\n",
    "        ans = []\n",
    "        for i in range(k, n - 2 * k + 1):\n",
    "            if (cur := s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]) > t:\n",
    "                ans = [pre[i - 1][1], i, suf[i + k][1]]\n",
    "                t = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        acc = list(accumulate(nums,initial=0))  # 以0为初始值进行累加和\n",
    "        pre = [[] for _ in range(n)]\n",
    "        suf = [[] for _ in range(n)]\n",
    "        t = idx = 0\n",
    "        for i in range(n - k + 1):\n",
    "            cur = acc[i+k] - acc[i]\n",
    "            if cur > t:\n",
    "                pre[i + k - 1] = [cur, i]\n",
    "                t, idx = pre[i + k - 1]\n",
    "            else:\n",
    "                pre[i + k - 1] = [t, idx]\n",
    "        t = idx = 0\n",
    "        for i in range(n-k,-1,-1):\n",
    "            cur = acc[i+k] - acc[i]\n",
    "            if cur >= t:\n",
    "                suf[i] = [cur,i]\n",
    "                t,idx = suf[i]\n",
    "            else:\n",
    "                suf[i] = t,idx\n",
    "        t = 0\n",
    "        ans = []\n",
    "        for i in range(k, n-2*k+1):\n",
    "            cur = pre[i-1][0] + suf[i+k][0] + acc[i+k] - acc[i]\n",
    "            if cur > t:\n",
    "                ans = [pre[i-1][1],i,suf[i+k][1]]\n",
    "                t = cur\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "\n",
    "        #先计算求和，问题简化到三个数字层面\n",
    "        s= [sum(nums[i:i+k]) for i in range(0,n-k+1) ]\n",
    "\n",
    "        #取值元素index，求和结果\n",
    "        first=[[0,0]]*(n-k+1)\n",
    "        first[0]=[0,s[0]]\n",
    "\n",
    "        for i in range(1,len(first)):\n",
    "            if first[i-1][1]>=s[i]:\n",
    "                first[i]=first[i-1]\n",
    "            else:\n",
    "                first[i]=[i,s[i]]\n",
    "\n",
    "        #first 元素index，second 元素index，求和结果\n",
    "        # second=[[0,0,0]]*(n-k+1)  #错误写法\n",
    "        second=[[0,0,0] for _ in range(n-k+1)]\n",
    "\n",
    "        for i in range(k,len(second)):\n",
    "            if first[i-k][1]+s[i]>second[i-1][2]:\n",
    "                second[i][0]=first[i-k][0]\n",
    "                second[i][1]=i\n",
    "                second[i][2]=first[i-k][1]+s[i]\n",
    "            else:\n",
    "                second[i]=second[i-1]\n",
    "\n",
    "        maxA=0\n",
    "        maxB=0\n",
    "        maxC=0\n",
    "        maxVal=0\n",
    "        for i in range(2*k,n-k+1):\n",
    "            if second[i-k][2]+s[i]>maxVal:\n",
    "                maxA=second[i-k][0]\n",
    "                maxB=second[i-k][1]\n",
    "                maxC=i\n",
    "                maxVal=second[i-k][2]+s[i]\n",
    "        \n",
    "        return [maxA,maxB,maxC]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = [0] * n\n",
    "        c = sum(nums[:k-1])\n",
    "        for i in range(k-1, n):\n",
    "            c += nums[i]\n",
    "            s[i-k+1] = c\n",
    "            c -= nums[i-k+1]\n",
    "\n",
    "        a, b, c = [[0, 0] for _ in range(n)], [[0, 0] for _ in range(n)], [[0, 0] for _ in range(n)]\n",
    "        \n",
    "        a[-k][0] = s[-k]\n",
    "        a[-k][1] = n - k\n",
    "        for i in range(n-k-1, -1, -1):\n",
    "            x = s[i]\n",
    "            y = a[i+1][0]\n",
    "            if x >= y:\n",
    "                a[i][0] = x\n",
    "                a[i][1] = i\n",
    "            else:\n",
    "                a[i][0] = y\n",
    "                a[i][1] = a[i+1][1]\n",
    "\n",
    "        b[-k*2][0] = s[-k*2] + a[-k][0]\n",
    "        b[-k*2][1] = n - k*2\n",
    "        for i in range(n - k*2 - 1, -1, -1):\n",
    "            x = s[i] + a[i+k][0]\n",
    "            y = b[i+1][0]\n",
    "            if x >= y:\n",
    "                b[i][0] = x\n",
    "                b[i][1] = i\n",
    "            else:\n",
    "                b[i][0] = y\n",
    "                b[i][1] = b[i+1][1]\n",
    "\n",
    "        c[-k*3][0] = s[-k*3] + b[-k*2][0]\n",
    "        c[-k*3][1] = n - k*3\n",
    "        for i in range(n - k*3 - 1, -1, -1):\n",
    "            x = s[i] + b[i+k][0]\n",
    "            y = c[i+1][0]\n",
    "            if x >= y:\n",
    "                c[i][0] = x\n",
    "                c[i][1] = i\n",
    "            else:\n",
    "                c[i][0] = y\n",
    "                c[i][1] = c[i+1][1]\n",
    "        \n",
    "        # print(c, \"\\n\", b, \"\\n\", a, \"\\n\")\n",
    "        ans = [0, 0, 0]\n",
    "        i = 0\n",
    "        ans[0] = c[i][1]\n",
    "        i = ans[0] + k\n",
    "        ans[1] = b[i][1]\n",
    "        i = ans[1] + k\n",
    "        ans[2] = a[i][1]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "# 思路\n",
    "\n",
    "# 递归dfs不会保存序号, 求大佬指点\n",
    "# 用传统dp,需要保存二维dp列表,不然压缩成一维的话,序号信息就丢失了,无法还原\n",
    "# dp注意\n",
    "\n",
    "# 明确dp的意义: dp: dp[i][c] 当前已经选择了c个物品, 当前已经看到了i种物品\n",
    "# 转移方程: 决定当前看到的这第i个物品要不要, 要则 dp[i][c] = dp[i - k][c-1] + goods[i]; 不要则 dp[i][c] = dp[i-1][c] 两个都是正方向\n",
    "        presum = [0]+list(accumulate(nums))#计算前缀和\n",
    "        \n",
    "        n = len(nums)\n",
    "        #以当前位置开始的长为k的子数组和\n",
    "        goods = [presum[i+k]- presum[i] for i in range(0, n - k + 1)]\n",
    "        row = len(goods) # col = 4\n",
    "        #dp: dp[i][c] 当前已经选择了c个物品, 当前已经看到了i种物品\n",
    "        dp = [[0]*4 for _ in range(row)]\n",
    "\n",
    "        for i in range(row):  #0,1,2,3.物品编号\n",
    "            for c in range(1,4):\n",
    "                # #初始化, i<k时不可能已经选择多于1个物品\n",
    "                # if i - k < 0 and c > 1: \n",
    "                #     dp[i][c] = - inf\n",
    "                # else:\n",
    "                dp[i][c] = max(dp[i - 1][c], dp[i - k][c-1] + goods[i])\n",
    "        print(dp)\n",
    "        #还原编号\n",
    "        v = 3\n",
    "        ii = row-1\n",
    "        ans_goods = []\n",
    "        while v > 0:\n",
    "            for i in range(row):\n",
    "                if dp[i][v] == dp[ii][v]:\n",
    "                    ans_goods += i,\n",
    "                    v = v - 1\n",
    "                    ii = i - k\n",
    "                    break\n",
    "        return ans_goods[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, pf: List[int], k: int) -> List[int]:\n",
    "        n = len(pf)\n",
    "        pf = [0] + pf\n",
    "        dp = [[0] * 4 for _ in range(n + 1)]\n",
    "        pos = [[0] * 4 for _ in range(n + 1)]\n",
    "        ma,ans = 0, [inf] * 3\n",
    "        for i in range(n + 1):\n",
    "            if i > 0:\n",
    "                pf[i] = pf[i - 1] + pf[i]\n",
    "            for j in range(1,4):\n",
    "                if i >= k * j:\n",
    "                    nk,np,ndp = pf[i] - pf[i - k], pos[i - 1][j], dp[i - 1][j]\n",
    "\n",
    "                    if dp[i - k][j - 1] + nk > dp[i - 1][j]:\n",
    "                        np = i\n",
    "                        ndp = dp[i - k][j - 1] + nk\n",
    "                    pos[i][j] = np\n",
    "                    dp[i][j] = ndp\n",
    "\n",
    "            if i >= 3 * k and dp[i][3] >= ma:\n",
    "                now,np,nk = [0] * 3,pos[i][3],3\n",
    "                while nk > 0:\n",
    "                    now[nk - 1] = pos[np][nk] - k\n",
    "                    nk -= 1\n",
    "                    np = pos[np - k][nk]\n",
    "                ans = now if dp[i][3] > ma else min(ans,now)\n",
    "                ma = dp[i][3]\n",
    "\n",
    "        return ans\n",
    "\n",
    "#    0   1   2   3\n",
    "# 1 [0,  0,  0,  0]\n",
    "# 2 [0,  3,  0,  0]\n",
    "# 3 [0,  3,  0,  0]\n",
    "# 4 [0,  3,  6,  0]\n",
    "# 5 [0,  8, 11,  0]\n",
    "# 6 [0, 13, 16, 19]\n",
    "# 7 [0, 13, 20, 23]\n",
    "# 8 [0, 13, 20, 23]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        f = [[0] * 3 for _ in range(n)]\n",
    "        g = [[-1] * 3 for _ in range(n)]\n",
    "        tot = 0\n",
    "        for j in range(k):\n",
    "            tot += nums[j]\n",
    "        f[k - 1][0] = tot\n",
    "        g[k - 1][0] = 0\n",
    "        for j in range(k, n):\n",
    "            tot += nums[j]\n",
    "            tot -= nums[j - k]\n",
    "            f[j][0] = f[j-1][0]\n",
    "            g[j][0] = g[j-1][0]\n",
    "            if tot > f[j-1][0]:\n",
    "                f[j][0] = tot\n",
    "                g[j][0] = j - k + 1\n",
    "\n",
    "        for i in range(1, 3):\n",
    "            tot = 0\n",
    "            for j in range(k * i, k * i + k):\n",
    "                tot += nums[j]\n",
    "            f[k * (i + 1) - 1][i] = tot + f[k * i - 1][i - 1]\n",
    "            g[k * (i + 1) - 1][i] = k * i\n",
    "            for j in range(k * (i + 1), n):\n",
    "                tot += nums[j]\n",
    "                tot -= nums[j - k]\n",
    "                f[j][i] = f[j-1][i]\n",
    "                g[j][i] = g[j-1][i]\n",
    "                if tot + f[j - k][i - 1] > f[j-1][i]:\n",
    "                    f[j][i] = tot + f[j - k][i - 1]\n",
    "                    g[j][i] = j - k + 1\n",
    "        # print(f)\n",
    "        # print(g)\n",
    "        ans = []\n",
    "        cur = n\n",
    "        for i in range(2, -1, -1):\n",
    "            print(cur)\n",
    "            ans.append(g[cur - 1][i])\n",
    "            cur = g[cur-1][i]\n",
    "        return sorted(ans)\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        for i in range(k):\n",
    "            s += nums[i]\n",
    "        d1 = [s]\n",
    "        d1s = [[0,s]]\n",
    "        for i in range(k,n):\n",
    "            s -= nums[i-k]\n",
    "            s += nums[i]\n",
    "            d1.append(s)\n",
    "            if s>d1s[-1][1]:\n",
    "                d1s.append([i-k+1,s])\n",
    "            else:\n",
    "                d1s.append(d1s[-1])\n",
    "        d2s = [[0,k,d1[0]+d1[k]]]\n",
    "        j = k+1\n",
    "        while(j<len(d1)):\n",
    "            s = d1s[j-k][1]+d1[j]\n",
    "            if s>d2s[-1][2]:\n",
    "                d2s.append([d1s[j-k][0],j,s])\n",
    "            else:\n",
    "                d2s.append(d2s[-1])\n",
    "            j+=1\n",
    "        d3s = [[0,k,2*k,d1[0]+d1[k]+d1[2*k]]]\n",
    "        j = 2*k+1\n",
    "        while(j<len(d1)):\n",
    "            s = d2s[j-2*k][2]+d1[j]\n",
    "            if s>d3s[-1][3]:\n",
    "                d3s.append([d2s[j-2*k][0],d2s[j-2*k][1],j,s])\n",
    "            else:\n",
    "                d3s.append(d3s[-1])\n",
    "            j+=1\n",
    "        return d3s[-1][:3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        # stat sum of k-len substring\n",
    "        cur_sum = sum(nums[0:k])\n",
    "        sum_k = [cur_sum]\n",
    "        for i in range(1, n-k+1):\n",
    "            cur_sum = cur_sum + (nums[i+k-1] - nums[i-1])\n",
    "            sum_k.append(cur_sum)\n",
    "        print(sum_k)\n",
    "        \n",
    "        # dynamic programming\n",
    "\n",
    "        # level 1\n",
    "        d1 = [0] * (n-k+1)\n",
    "        idx1 = [None] * (n-k+1)\n",
    "        for i in range(n-k+1):\n",
    "            taken = sum_k[i]\n",
    "            no_taken = d1[i-1] if i>0 else -9999\n",
    "            if taken > no_taken:\n",
    "                d1[i] = taken\n",
    "                idx1[i] = [i]\n",
    "            else:\n",
    "                d1[i] = no_taken\n",
    "                idx1[i] = idx1[i-1]\n",
    "        print(d1, idx1)\n",
    "\n",
    "        # level 2\n",
    "        d2 = [-9999] * (n-k+1)\n",
    "        idx2 = [None] * (n-k+1)\n",
    "        for i in range(k, n-k+1):\n",
    "            taken = (sum_k[i] + d1[i-k])\n",
    "            no_taken = d2[i-1]\n",
    "            if taken > no_taken:\n",
    "                d2[i] = taken\n",
    "                idx2[i] = (idx1[i-k] + [i])\n",
    "            else:\n",
    "                d2[i] = no_taken\n",
    "                idx2[i] = idx2[i-1]\n",
    "        print(d2, idx2)\n",
    "\n",
    "        # level 3\n",
    "        d3 = [-9999] * (n-k+1)\n",
    "        idx3 = [None] * (n-k+1)\n",
    "        for i in range(2*k, n-k+1):\n",
    "            taken = (sum_k[i] + d2[i-k])\n",
    "            no_taken = d3[i-1]\n",
    "            if taken > no_taken:\n",
    "                d3[i] = taken\n",
    "                idx3[i] = idx2[i-k] + [i]\n",
    "            else:\n",
    "                d3[i] = no_taken\n",
    "                idx3[i] = idx3[i-1]\n",
    "\n",
    "        # print(d3, idx3)\n",
    "        return idx3[-1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        dp=[[0]*n for _ in range(3)]\n",
    "        sums=[sum(nums[:i+1]) for i in range(n)]\n",
    "        dp[0][k-1]=sums[k-1]\n",
    "        dp[1][2*k-1]=sums[2*k-1]\n",
    "        dp[2][3*k-1]=sums[3*k-1]\n",
    "        ans1=[0]*n\n",
    "        ans2=[[0,k] for _ in range(n)]\n",
    "        ans3=[[0,k,2*k] for _ in range(n)]\n",
    "\n",
    "        for i in range(k,n):\n",
    "            temp0=sums[i]-sums[i-k]\n",
    "            if dp[0][i-1]<temp0:\n",
    "                dp[0][i]=temp0\n",
    "                ans1[i]=i-k+1\n",
    "            else:\n",
    "                dp[0][i]=dp[0][i-1]\n",
    "                ans1[i]=ans1[i-1]\n",
    "            if i>=2*k:\n",
    "                temp1=dp[0][i-k]+sums[i]-sums[i-k]\n",
    "                if dp[1][i-1]<temp1:\n",
    "                    dp[1][i]=temp1\n",
    "                    ans2[i]=[ans1[i-k],i-k+1]\n",
    "                else:\n",
    "                    dp[1][i]=dp[1][i-1]\n",
    "                    ans2[i]=ans2[i-1]\n",
    "            if i>=3*k:\n",
    "                temp2=dp[1][i-k]+sums[i]-sums[i-k]\n",
    "                if dp[2][i-1]<temp2:\n",
    "                    dp[2][i]=temp2\n",
    "                    ans3[i]=[ans2[i-k][0],ans2[i-k][1],i-k+1]\n",
    "                else:\n",
    "                    dp[2][i]=dp[2][i-1]\n",
    "                    ans3[i]=ans3[i-1]\n",
    "        return ans3[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cur = 0\n",
    "        for i in range(k):\n",
    "            cur += nums[i]\n",
    "        ns = [cur]\n",
    "        for i in range(k, n):\n",
    "            cur += nums[i] - nums[i - k]\n",
    "            ns.append(cur)\n",
    "        \n",
    "        m = n - k + 1\n",
    "        dp = [(0, []) * 2 for _ in range(m)] # python 2nd array\n",
    "\n",
    "        mv = 0\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            if i > 0:\n",
    "                dp[i] = deepcopy(dp[i - 1])\n",
    "            else:\n",
    "                dp[i] = [(0, []), (0, [])]\n",
    "            \n",
    "            if i == 0 or ns[i] > dp[i - 1][0][0]:\n",
    "                dp[i][0] = [ns[i], [i]]\n",
    "\n",
    "            if i >= k:\n",
    "                t = ns[i] + dp[i - k][0][0]\n",
    "                if dp[i][1][0] < t:\n",
    "                    dp[i][1] = (t, dp[i - k][0][1] + [i])\n",
    "            \n",
    "            if i >= 2 * k: \n",
    "                t = ns[i] + dp[i - k][1][0]\n",
    "                if t > mv:\n",
    "                    mv = t\n",
    "                    ans = dp[i - k][1][1] + [i]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        subsums = [0] * n\n",
    "        subsums[k - 1] = sum(nums[:k])\n",
    "        for i in range(k, n):\n",
    "            subsums[i] = subsums[i - 1] + nums[i] - nums[i - k]\n",
    "        \n",
    "        dp1 = [[0, -1] for _ in range(n + 1)]\n",
    "        dp2 = [[0, -1, -1] for _ in range(n + 1)]\n",
    "        dp3 = [[0, -1, -1, -1] for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            if subsums[i] > dp1[i][0]:\n",
    "                dp1[i + 1] = [subsums[i], i - k + 1]\n",
    "            else:\n",
    "                dp1[i + 1] = [dp1[i][0], dp1[i][1]]\n",
    "            if dp1[max(i - k + 1, 0)][0] + subsums[i] > dp2[max(i, 0)][0]:\n",
    "                dp2[i + 1] = [dp1[max(i - k + 1, 0)][0] + subsums[i], dp1[max(i - k + 1, 0)][1], i - k + 1]\n",
    "            else:\n",
    "                dp2[i + 1] = [dp2[i][0], dp2[i][1], dp2[i][2]]\n",
    "            if dp2[max(i - k + 1, 0)][0] + subsums[i] > dp3[max(i, 0)][0]:\n",
    "                dp3[i + 1] = [dp2[max(i - k + 1, 0)][0] + subsums[i], dp2[max(i - k + 1, 0)][1], dp2[max(i - k + 1, 0)][2], i - k + 1]\n",
    "            else:\n",
    "                dp3[i + 1] = [dp3[i][0], dp3[i][1], dp3[i][2], dp3[i][3]]\n",
    "        return dp3[n][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n+1)  # 前缀和数组\n",
    "        # ones[i]为一个在nums[:i+1]中，长度为k，且数字和最大的子数组\n",
    "        # ones[i][0]记录的是起始index，ones[i][1]记录的是最大和\n",
    "        ones = [[[], 0] for _ in range(n)]\n",
    "        # twos[i]为两个在nums[:i+1]中，长度为k，且数字和最大的子数组\n",
    "        twos = [[[], 0] for _ in range(n)]\n",
    "        num = 0\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            s[i+1] = s[i] + nums[i]\n",
    "            diff = s[i+1] - (s[i+1-k] if i >= k-1 else 0)\n",
    "            if i >= k-1:\n",
    "                if ones[i-1][1] < diff:\n",
    "                    ones[i][0] = [i-k+1]\n",
    "                    ones[i][1] = diff\n",
    "                else:\n",
    "                    ones[i][0] = ones[i-1][0]\n",
    "                    ones[i][1] = ones[i-1][1]\n",
    "            if i >= 2*k-1:\n",
    "                diff += ones[i-k][1]\n",
    "                if twos[i-1][1] < diff:\n",
    "                    twos[i][0] = ones[i-k][0] + [i-k+1]\n",
    "                    twos[i][1] = diff\n",
    "                else:\n",
    "                    twos[i][0] = twos[i-1][0]\n",
    "                    twos[i][1] = twos[i-1][1]\n",
    "                diff -= ones[i-k][1]\n",
    "            if i >= 3*k - 1:\n",
    "                diff += twos[i-k][1]\n",
    "                if num < diff:\n",
    "                    res = twos[i-k][0] + [i-k+1]\n",
    "                    num = diff\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        test = []\n",
    "        total = sum(nums[:k])\n",
    "        test.append(total)\n",
    "        for i in range(k, len(nums)):\n",
    "            total += nums[i] - nums[i - k]\n",
    "            test.append(total)\n",
    "        print(test)\n",
    "        dp = [[] for _ in range(3)]\n",
    "        for i in range(len(test)):\n",
    "            if len(dp[0]) == 0 or test[i] > dp[0][-1][0]:\n",
    "                dp[0].append((test[i], -i))\n",
    "            else:\n",
    "                dp[0].append(dp[0][-1])\n",
    "        for i in range(1, 3):\n",
    "            for j in range(i * k, len(test)):\n",
    "                if len(dp[i]) == 0 or test[j] + dp[i - 1][j - k * i][0] > dp[i][-1][0]:\n",
    "                    dp[i].append((test[j] + dp[i - 1][j - k * i][0], -j))\n",
    "                else:\n",
    "                    dp[i].append(dp[i][-1])\n",
    "        res = []\n",
    "        x = -dp[-1][-1][1]\n",
    "        print(dp)\n",
    "        res.append(x)\n",
    "        x = -dp[i - 1][x - k - k][1]\n",
    "        res.append(x)\n",
    "        x = -dp[i - 2][x - k][1]\n",
    "        res.append(x)\n",
    "        return res[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        preSum = []\n",
    "        cur = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur += nums[i]\n",
    "            if i >= k:\n",
    "                cur -= nums[i - k]\n",
    "            if i >= k-1:\n",
    "                preSum.append(cur)\n",
    "\n",
    "        # print(preSum)\n",
    "\n",
    "        maxIdx = [[[] for _ in range(3)] for _ in range(len(preSum))]\n",
    "        maxScore = [[-float(\"inf\"), -float(\"inf\"), -float(\"inf\")] for _ in range(len(preSum))]\n",
    "        maxIdx[0][0] = [0]\n",
    "        maxScore[0][0] = preSum[0]\n",
    "        # print(maxIdx)\n",
    "        for i in range(1, len(preSum)):\n",
    "            for j in range(min(i + 1, 3) - 1, -1, -1):\n",
    "                if j == 0:\n",
    "                    if preSum[i] <= maxScore[i - 1][j]:\n",
    "                        maxScore[i][j] = maxScore[i - 1][0]\n",
    "                        # print(maxIdx[i-1])\n",
    "                        maxIdx[i][j] = maxIdx[i - 1][0]\n",
    "                    else:\n",
    "                        maxScore[i][j] = preSum[i]\n",
    "                        maxIdx[i][j] = [i]\n",
    "                else:\n",
    "                    if i < k or preSum[i] + maxScore[i - k][j - 1] <= maxScore[i-1][j]:\n",
    "                        maxScore[i][j] = maxScore[i - 1][j]\n",
    "                        maxIdx[i][j] = maxIdx[i - 1][j][:]\n",
    "                    else:\n",
    "                        maxScore[i][j] = maxScore[i - k][j - 1] + preSum[i]\n",
    "                        maxIdx[i][j] = maxIdx[i - k][j - 1] + [i]\n",
    "            # print(maxScore, maxIdx)\n",
    "        return [int(x) for x in maxIdx[-1][-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        subsums = [0] * n\n",
    "        subsums[k - 1] = sum(nums[:k])\n",
    "        for i in range(k, n):\n",
    "            subsums[i] = subsums[i - 1] + nums[i] - nums[i - k]\n",
    "        \n",
    "        dp1 = [[0, -1] for _ in range(n + 1)]\n",
    "        dp2 = [[0, -1, -1] for _ in range(n + 1)]\n",
    "        dp3 = [[0, -1, -1, -1] for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            if subsums[i] > dp1[i][0]:\n",
    "                dp1[i + 1] = [subsums[i], i - k + 1]\n",
    "            else:\n",
    "                dp1[i + 1] = [*dp1[i]]\n",
    "            if dp1[max(i - k + 1, 0)][0] + subsums[i] > dp2[max(i, 0)][0]:\n",
    "                dp2[i + 1] = [dp1[max(i - k + 1, 0)][0] + subsums[i], *dp1[max(i - k + 1, 0)][1:], i - k + 1]\n",
    "            else:\n",
    "                dp2[i + 1] = [*dp2[i]]\n",
    "            if dp2[max(i - k + 1, 0)][0] + subsums[i] > dp3[max(i, 0)][0]:\n",
    "                dp3[i + 1] = [dp2[max(i - k + 1, 0)][0] + subsums[i], *dp2[max(i - k + 1, 0)][1:], i - k + 1]\n",
    "            else:\n",
    "                dp3[i + 1] = [*dp3[i]]\n",
    "        return dp3[n][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # 若相等返回右边的参数，所以传入参数时将字典序小的放右边\n",
    "        def lmax(l1, l2):\n",
    "            if l1[0] > l2[0]:\n",
    "                return l1\n",
    "            return l2\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        wins = [presum[i + k] - presum[i] for i in range(n - k + 1)]\n",
    "        # dp[i]对应wins[i]的状态，表示当前选第一个，第二个，第三个子数组时对应的最大值和坐标\n",
    "        dp = [[[0,-1]] * 3 for _ in range(len(wins))]\n",
    "        for i, w in enumerate(wins):\n",
    "            # 只能选第一个\n",
    "            if i < k:\n",
    "                dp[i][0] = lmax([w, i], dp[i - 1][0])\n",
    "            else:\n",
    "                dp[i][0] = lmax([w, i], dp[i - 1][0])\n",
    "                dp[i][1] = lmax([w + dp[i - k][0][0], (dp[i - k][0][1], i)], dp[i - 1][1])\n",
    "                if i >= k * 2:\n",
    "                    dp[i][2] = lmax([w + dp[i - k][1][0], (dp[i - k][1][1][0], dp[i - k][1][1][1], i)], dp[i - 1][2])\n",
    "        return dp[-1][-1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums, k):\n",
    "        n = len(nums)\n",
    "\n",
    "        # 计算前缀和数组\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]\n",
    "\n",
    "        # 初始化动态规划数组\n",
    "        dp = [[0] * (n + 1) for _ in range(4)]\n",
    "        indexes = [[[] for _ in range(n + 1)] for _ in range(4)]\n",
    "\n",
    "        # 动态规划过程\n",
    "        for i in range(1, 4):\n",
    "            for j in range(k, n + 1):\n",
    "                # 不选当前子数组\n",
    "                dp[i][j] = dp[i][j - 1]\n",
    "                indexes[i][j] = indexes[i][j - 1]\n",
    "\n",
    "                # 选当前子数组\n",
    "                current_sum = prefix_sum[j] - prefix_sum[j - k]\n",
    "                previous_sum = dp[i - 1][j - k] if j >= k else 0\n",
    "\n",
    "                if current_sum + previous_sum > dp[i][j]:\n",
    "                    dp[i][j] = current_sum + previous_sum\n",
    "                    indexes[i][j] = indexes[i - 1][j - k] + [j - k]\n",
    "\n",
    "        return indexes[3][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        acc = list(accumulate(nums[::-1])) + [0]\n",
    "        dp = [[0] * 4 for _ in range(n)]\n",
    "        idx = [[[-1, -1, -1] for i in range(4)] for j in range(n)]\n",
    "        for i in range(k - 1, n):\n",
    "            for j in range(1, 4):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                for l in range(3):\n",
    "                    idx[i][j][l] = idx[i - 1][j][l]\n",
    "                if dp[i][j] <= dp[i - k][j - 1] + acc[i] - acc[i - k]:\n",
    "                    dp[i][j] = dp[i - k][j - 1] + acc[i] - acc[i - k]\n",
    "                    for l in range(3):\n",
    "                        idx[i][j][l] = idx[i - k][j - 1][l] if l != j - 1 else i - k + 1\n",
    "        return [n - i - k for i in idx[n - 1][3]][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cur = 0\n",
    "        for i in range(k):\n",
    "            cur += nums[i]\n",
    "        ns = [cur]\n",
    "        for i in range(k, n):\n",
    "            cur += nums[i] - nums[i - k]\n",
    "            ns.append(cur)\n",
    "        \n",
    "        m = n - k + 1\n",
    "        dp = [(0, []) * 3 for _ in range(m)] # python 2nd array\n",
    "\n",
    "        mv = 0\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            if i > 0:\n",
    "                dp[i] = deepcopy(dp[i - 1])\n",
    "            else:\n",
    "                dp[i] = [(0, []), (0, []), (0, [])]\n",
    "            \n",
    "            if i == 0 or ns[i] > dp[i - 1][0][0]:\n",
    "                dp[i][0] = [ns[i], [i]]\n",
    "\n",
    "            if i >= k:\n",
    "                t = ns[i] + dp[i - k][0][0]\n",
    "                if dp[i][1][0] < t:\n",
    "                    dp[i][1] = (t, dp[i - k][0][1] + [i])\n",
    "            \n",
    "            if i >= 2 * k: \n",
    "                t = ns[i] + dp[i - k][1][0]\n",
    "                if dp[i][2][0] < t:\n",
    "                    dp[i][2] = (t, dp[i - k][1][1] + [i])\n",
    "\n",
    "                    if dp[i][2][0] >= mv:\n",
    "                        mv = dp[i][2][0]\n",
    "                        ans = dp[i][2][1]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        sp = []\n",
    "        sp.append(sum(nums[:k]))\n",
    "        for i in range(len(nums)-k):\n",
    "            sp.append(sp[-1]-nums[i]+nums[i+k])\n",
    "        \n",
    "        #print(sp)\n",
    "\n",
    "        dp = [[[] for j in range(3)] for i in range(len(sp))]\n",
    "\n",
    "        dp[0][0] = [sp[0],[0]]\n",
    "\n",
    "        for i in range(1,len(sp)):\n",
    "            if sp[i] > dp[i-1][0][0]:\n",
    "                dp[i][0] = [sp[i],[i]]\n",
    "            else:\n",
    "                dp[i][0] = list(dp[i-1][0])\n",
    "            \n",
    "            if i == k:\n",
    "                dp[i][1] = [sp[i] + dp[i-k][0][0], [0,k]]\n",
    "            if i > k:\n",
    "                if sp[i] + dp[i-k][0][0] > dp[i-1][1][0]:\n",
    "                    dp[i][1] = [sp[i] + dp[i-k][0][0], list(dp[i-k][0][1]) + [i]]\n",
    "                else:\n",
    "                    dp[i][1] = list(dp[i-1][1])\n",
    "            \n",
    "            if i == k * 2:\n",
    "                dp[i][2] = [sp[i] + dp[i-k][1][0], [0,k,k*2]]\n",
    "            if i > k * 2:\n",
    "                if sp[i] + dp[i-k][1][0] > dp[i-1][2][0]:\n",
    "                    dp[i][2] = [sp[i] + dp[i-k][1][0], list(dp[i-k][1][1]) + [i]]\n",
    "                else:\n",
    "                    dp[i][2] = list(dp[i-1][2])\n",
    "        \n",
    "            #print(i,dp[i])\n",
    "        \n",
    "        return dp[-1][2][1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n < 3*k: return None\n",
    "        if n == 3*k: return [i for i in range(0, n, k)]\n",
    "        res = [[[],[],[]] for _ in range(n)]\n",
    "        tmp_sum_k = sum(nums[:k])\n",
    "        res[0] = [[tmp_sum_k, [0]] for _ in range(3)]\n",
    "        for i in range(1,n):\n",
    "            if i > 0:\n",
    "                head_diff = nums[i-1]\n",
    "                tail_diff = (nums[i+k-1] if i+k-1 < n else 0)\n",
    "                tmp_sum_k = (tmp_sum_k - head_diff + tail_diff)\n",
    "            pre_idx = i - k\n",
    "            for j in range(3):\n",
    "                pre_cnt = j-1\n",
    "                if pre_idx < 0 or pre_cnt < 0:\n",
    "                    tmp_sum = tmp_sum_k\n",
    "                    tmp_idx = [i]\n",
    "                else:\n",
    "                    tmp_sum = tmp_sum_k + res[pre_idx][pre_cnt][0]\n",
    "                    tmp_idx = res[pre_idx][pre_cnt][1] + [i]\n",
    "                if tmp_sum > res[i-1][j][0]:\n",
    "                    res[i][j] = [tmp_sum, tmp_idx]\n",
    "                else:\n",
    "                    res[i][j] = res[i-1][j]\n",
    "        return res[-1][-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        s = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            s[i+1] = s[i] + nums[i]\n",
    "            \n",
    "        p = [[(-inf, [])]*3 for _ in range(n)]\n",
    "        p[k-1][0] = (s[k], [0])\n",
    "        for i in range(k, n):\n",
    "            p[i] = p[i-1].copy()\n",
    "            t = s[i+1] - s[i-k+1]\n",
    "            # first\n",
    "            if (t > p[i-1][0][0]):\n",
    "                p[i][0] = (t, [i-k+1])\n",
    "            #second\n",
    "            if (i >= 2*k - 1):\n",
    "                if (t + p[i-k][0][0]) > p[i][1][0]:\n",
    "                    p[i][1] = (t + p[i-k][0][0], p[i-k][0][1]+[i-k+1])\n",
    "            #third\n",
    "            if (i >= 3*k-1):\n",
    "                if (t + p[i-k][1][0]) > p[i][2][0]:\n",
    "                    p[i][2] = (t + p[i-k][1][0], p[i-k][1][1] + [i-k+1])\n",
    "\n",
    "        return p[-1][2][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        bit = 3\n",
    "        pre = [0]\n",
    "        for c in nums:\n",
    "            pre.append(pre[-1] + c)\n",
    "        n = len(nums)\n",
    "        # dp[i][j]代表j个不重叠子数组的最大和\n",
    "        dp = [[0] + [-float('inf')] * bit for _ in range(n)]\n",
    "        # d[i][j]代表j个不重叠子数组的位置\n",
    "        d = [[[] for j in range(bit + 1)] for i in range(n)]\n",
    "        for j in range(1, bit + 1):\n",
    "            for i in range(j * k - 1, n):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                d[i][j] = d[i - 1][j].copy()\n",
    "                cnt = pre[i + 1] - pre[i + 1 - k] + dp[i - k][j - 1]\n",
    "                if cnt > dp[i][j]:\n",
    "                    dp[i][j] = cnt\n",
    "                    d[i][j] = d[i - k][j - 1].copy() + [i - k + 1]\n",
    "        return d[-1][bit]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        dp = [ [ [ 0 , [0] ], [ 0, [0,0] ], [ 0 , [0,0,0] ] ] for i in range(len(nums)+1) ]\n",
    "        idx = k\n",
    "        while idx <= len(nums):\n",
    "            tmp_sum = sum(nums[ idx-k : idx ] )\n",
    "            if tmp_sum > dp[idx-1][0][0]:\n",
    "                dp[idx][0] = [ tmp_sum , [idx-k] ]\n",
    "            else:\n",
    "                dp[idx][0] = dp[idx-1][0]\n",
    "            if tmp_sum + dp[idx-k][0][0] > dp[idx-1][1][0]:\n",
    "                dp[idx][1] = [ tmp_sum + dp[idx-k][0][0] , (dp[idx-k][0][1][0], idx-k ) ]\n",
    "            else:\n",
    "                dp[idx][1] = dp[idx-1][1]\n",
    "            if tmp_sum + dp[idx-k][1][0] > dp[idx-1][2][0]:\n",
    "                dp[idx][2] = [ tmp_sum + dp[idx-k][1][0] , (dp[idx-k][1][1][0], dp[idx-k][1][1][1], idx-k ) ]\n",
    "            else:\n",
    "                dp[idx][2] = dp[idx-1][2]\n",
    "            print(dp[idx])\n",
    "            idx += 1\n",
    "        return list(dp[-1][-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseTable:\n",
    "    def __init__(self, nums, func):\n",
    "        self.func = func\n",
    "        nums = list(nums)\n",
    "        n = len(nums)\n",
    "        self.n = n\n",
    "        self.lg = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            self.lg[i] = self.lg[i // 2] + 1\n",
    "        self.t = [nums] + [[0] * n for _ in range(self.lg[n])]\n",
    "        for i in range(1, self.lg[n] + 1):\n",
    "            step = 1 << i - 1\n",
    "            for j in range(n - step * 2 + 1):\n",
    "                self.t[i][j] = func(self.t[i - 1][j], self.t[i - 1][j + step])\n",
    "\n",
    "    def get(self, l: int, r: int): # left-closed, right-open.\n",
    "        if l >= r or l < 0 or r > self.n:\n",
    "            return -1 # default value\n",
    "        depth = self.lg[r - l]\n",
    "        return self.func(self.t[depth][l], self.t[depth][r - (1 << depth)])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cur = 0\n",
    "        for i in range(k):\n",
    "            cur += nums[i]\n",
    "        ns = [cur]\n",
    "        for i in range(k, n):\n",
    "            cur += nums[i] - nums[i - k]\n",
    "            ns.append(cur)\n",
    "        \n",
    "        st = SparseTable(ns, max)\n",
    "        m = n - k + 1\n",
    "        dp = [(0, []) * 3 for _ in range(m)] # python 2nd array\n",
    "\n",
    "        mv = 0\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            if i > 0:\n",
    "                dp[i] = deepcopy(dp[i - 1])\n",
    "            else:\n",
    "                dp[i] = [(0, []), (0, []), (0, [])]\n",
    "            \n",
    "            if i == 0 or ns[i] > dp[i - 1][0][0]:\n",
    "                dp[i][0] = [ns[i], [i]]\n",
    "\n",
    "            if i >= k:\n",
    "                t = ns[i] + dp[i - k][0][0]\n",
    "                if dp[i][1][0] < t:\n",
    "                    dp[i][1] = (t, dp[i - k][0][1] + [i])\n",
    "            \n",
    "            if i >= 2 * k: \n",
    "                t = ns[i] + dp[i - k][1][0]\n",
    "                if dp[i][2][0] < t:\n",
    "                    dp[i][2] = (t, dp[i - k][1][1] + [i])\n",
    "\n",
    "                    if dp[i][2][0] >= mv:\n",
    "                        mv = dp[i][2][0]\n",
    "                        ans = dp[i][2][1]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        # dp[i][j]表示到数组第j个元素为止，前i个互不重叠子数组的最大值。\n",
    "        # 对于当前第j个元素所对应值，有取或不取两种选择：\n",
    "        # 选择不取时，则值为到j-1个元素为止前i个互不重叠子数组的最大值，即dp[i][j-1]；\n",
    "        # 选择取时，则值为到j-k个元素为止前i-1个互不重叠子数组的最大值，再加上最后一段子数组的和，即dp[i-1][j-k]+sum[j]-sum[j-k]，其中sum为前缀和数组。\n",
    "        # dp[i][j] = max(dp[i][j-1], dp[i-1][j-k]+sum[j]-sum[j-k])\n",
    "        pre_sum = [0] + list(itertools.accumulate(nums))\n",
    "        N = len(nums)\n",
    "        dp = [[[0, []] for _ in range(N+1)] for _ in range(4)]\n",
    "        for i in range(1, 4):\n",
    "            for j in range(i*k, N+1):\n",
    "                drop, select = dp[i][j-1][0], dp[i-1][j-k][0] + pre_sum[j] - pre_sum[j-k]\n",
    "                if select > drop:\n",
    "                    dp[i][j] = [select, dp[i-1][j-k][1] + [j-k]]\n",
    "                else:\n",
    "                    dp[i][j] = [drop, dp[i][j-1][1]]\n",
    "        return dp[3][N][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ps = list(accumulate(nums, initial=0)) # 前缀和\n",
    "        # @cache\n",
    "        # def dfs(i, cnt):\n",
    "        #     if cnt == 0:\n",
    "        #         return (0, [])\n",
    "        #     if len(nums) - i < k:\n",
    "        #         return (-inf, [])\n",
    "        #     # 选\n",
    "        #     mx1, lst1 = dfs(i + k, cnt - 1)\n",
    "        #     mx1 += ps[i + k] - ps[i]\n",
    "        #     lst1 = [-i] + lst1\n",
    "        #     # 不选\n",
    "        #     mx2 ,lst2 = dfs(i + 1, cnt)\n",
    "        #     return max((mx1, lst1), (mx2, lst2))\n",
    "        \n",
    "        # mx, ans = dfs(0, 3)\n",
    "        # dfs.cache_clear()\n",
    "        n=len(nums)\n",
    "        f=[[(-inf,[]) for _ in range(4)] for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            f[i][0]=(0,[])\n",
    "        for i in range(n-k,-1,-1):\n",
    "            for cnt in range(1,4):\n",
    "                mx1,lst1=f[i+k][cnt-1]\n",
    "                mx1 += ps[i + k] - ps[i]\n",
    "                lst1 = [-i] + lst1\n",
    "                mx2 ,lst2 = f[i + 1][cnt]\n",
    "                f[i][cnt]=max((mx1, lst1), (mx2, lst2))\n",
    "        mx,ans=f[0][3]\n",
    "        ans = [-i for i in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ps = []\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                ps.append(nums[i])\n",
    "            else:\n",
    "                ps.append(ps[-1]+nums[i])\n",
    "\n",
    "        dp = [[(float('-inf'), [])]*4 for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            dp[i][0] = (0, [])\n",
    "        \n",
    "        for i in range(k-1, len(nums)):\n",
    "            j = i-k\n",
    "            if j < 0:\n",
    "                dp[i][1] = (ps[i], [j+1])\n",
    "            else:\n",
    "                d = ps[i]-ps[j]\n",
    "                for p in range(1, 4):\n",
    "                    if i > 0:\n",
    "                        dp[i][p] = dp[i-1][p]\n",
    "                    if dp[j][p-1][0]+d > dp[i][p][0]:\n",
    "                        dp[i][p] = (dp[j][p-1][0]+d, dp[j][p-1][1]+[j+1])\n",
    "        \n",
    "        max_s, ans = 0, None\n",
    "        for i in range(len(nums)):\n",
    "            if max_s < dp[i][-1][0]:\n",
    "                max_s, ans = dp[i][-1]\n",
    "\n",
    "        return ans \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        rec = {}\n",
    "        f = [[float('-inf')] * 3 for _ in range(len(nums) - k + 1)]\n",
    "        s = [0] * (len(nums) - k + 1)\n",
    "        temp_sum = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            temp_sum += nums[i]\n",
    "        s[0] = temp_sum\n",
    "        for i in range(k, len(nums)):\n",
    "            temp_sum -= (nums[i - k] - nums[i])\n",
    "            s[i - k + 1] = temp_sum\n",
    "\n",
    "        f[0][2] = s[0]\n",
    "        rec[(0, 2)] = (0, 3)\n",
    "        for i in range(1, len(nums) - k + 1):\n",
    "            f[i][2] = max(f[i - 1][2], s[i])\n",
    "            # 要求字典序最小的\n",
    "            if f[i][2] == f[i - 1][2]:\n",
    "                rec[(i, 2)] = (i - 1, 2)\n",
    "            else:\n",
    "                rec[(i, 2)] = (i, 3)\n",
    "            if i >= k:\n",
    "                # 要求字典序最小的\n",
    "                f[i][1] = max(f[i - 1][1], f[i - k][2] + s[i])\n",
    "                if f[i][1] == f[i - 1][1]:\n",
    "                    rec[(i, 1)] = (i - 1, 1)\n",
    "                else:\n",
    "                    rec[(i, 1)] = (i - k, 2)\n",
    "                f[i][0] = max(f[i - 1][0], f[i - k][1] + s[i])\n",
    "                if f[i][0] == f[i - 1][0]:\n",
    "                    rec[(i, 0)] = (i - 1, 0)\n",
    "                else:\n",
    "                    rec[(i, 0)] = (i - k, 1)\n",
    "        \n",
    "        ans = []\n",
    "        start, level = len(f) - 1, 0\n",
    "        while level != 3:\n",
    "            new_start, new_level = rec[(start, level)]\n",
    "            if new_level == level + 1:\n",
    "                ans.append(start)\n",
    "\n",
    "            start, level = new_start, new_level\n",
    "\n",
    "        return sorted(ans)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums) - k + 1\n",
    "        sumk = [0 for i in range(n)]\n",
    "        sumk[0] = sum(nums[:k])\n",
    "        for i in range(1, n):\n",
    "            sumk[i] = sumk[i - 1] + nums[i + k - 1] - nums[i - 1]\n",
    "        print(sumk)\n",
    "        dp = [[[0, [-1, -1, -1]] for i in range(n)] for j in range(4)]\n",
    "        for i in range(1, 4):\n",
    "            for j in range(i * k - k, n):\n",
    "                print(i, j, dp[i - 1][j - k][0], sumk[j], dp[i][j - 1][0])\n",
    "                if dp[i - 1][j - k][0] + sumk[j] > dp[i][j - 1][0]:\n",
    "                    dp[i][j][0] = dp[i - 1][j - k][0] + sumk[j]\n",
    "                    dp[i][j][1] = dp[i - 1][j - k][1][:]\n",
    "                    dp[i][j][1][i - 1] = j\n",
    "                else:\n",
    "                    dp[i][j][0] = dp[i][j - 1][0]\n",
    "                    dp[i][j][1] = dp[i][j - 1][1][:]\n",
    "        return dp[3][n - 1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        assert 3 * k <= len(nums)\n",
    "        # init\n",
    "        maps = {}\n",
    "        dp = [[0] * 4 for _ in range(len(nums) + 1)]\n",
    "        presum = [0]\n",
    "        for num in nums:\n",
    "            presum.append(num + presum[-1])\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                if i < j * k:\n",
    "                    dp[i][j] = float(\"-inf\")\n",
    "                else:\n",
    "                    dp[i][j] = max(\n",
    "                        c1 := dp[i-1][j],\n",
    "                        c2 := dp[i-k][j-1] + presum[i] - presum[i-k]  # sum(nums[i-k:i])\n",
    "                    )\n",
    "                    if c1 < c2:\n",
    "                        maps[(i, j)] = maps.get((i-k, j-1), []) + [i-k]\n",
    "                    else:\n",
    "                        maps[(i, j)] = maps[(i-1, j)]\n",
    "               \n",
    "        ans = [float(\"inf\")]\n",
    "        value = float(\"-inf\")\n",
    "        for i in range(len(dp)-1, 0, -1):\n",
    "            if value <= dp[i][-1]:\n",
    "                value = dp[i][-1]\n",
    "                ans = min(ans, maps[(i, 3)])    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        total = sum(nums[:k])\n",
    "        sums = [total]\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            total += nums[i]\n",
    "            total -= nums[i - k]\n",
    "            sums.append(total)\n",
    "\n",
    "        # sums[0] [0, k)\n",
    "        # sums[1] [1, k + 1]\n",
    "        \n",
    "        cache = {}\n",
    "        def helper(index, left):\n",
    "            if left == 0:\n",
    "                return []\n",
    "\n",
    "            if index >= len(sums):\n",
    "                return [-1]\n",
    "\n",
    "            key = (index, left)\n",
    "            if key not in cache:\n",
    "                taken = helper(index + k, left - 1)\n",
    "    \n",
    "                if taken == [-1]:\n",
    "                    cache[key] = [-1]\n",
    "                else:\n",
    "                    not_taken = helper(index + 1, left)\n",
    "                    s1 = sum(sums[i] for i in taken + [index])\n",
    "                    s2 =  sum(sums[i] for i in not_taken)\n",
    "    \n",
    "                    if s1 >= s2:\n",
    "                        cache[key] = [index] + taken\n",
    "                    else:\n",
    "                        cache[key] = not_taken\n",
    "            \n",
    "            return cache[key]\n",
    "\n",
    "        return  helper(0, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dp = [[[0, [0, 0, 0]]  for _ in range(n)] for _ in range(4)]\n",
    "\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum[i + 1] = presum[i] + nums[i]\n",
    "        \n",
    "        dp[1][k - 1][0] = presum[k]\n",
    "        dp[1][k - 1][1] = [0, 0, 0]\n",
    "        dp[2][2 * k - 1][0] = presum[2 * k]\n",
    "        dp[2][2 * k - 1][1] = [0, k, 0]\n",
    "        dp[3][3 * k - 1][0] = presum[3 * k]\n",
    "        dp[3][3 * k - 1][1] = [0, k, 2 * k]\n",
    "        for i in range(k, 2 * k):\n",
    "            if presum[i + 1] - presum[i - k + 1] > dp[1][i - 1][0]:\n",
    "                dp[1][i][0] = presum[i + 1] - presum[i - k + 1]\n",
    "                dp[1][i][1] = [i - k + 1, 0, 0]\n",
    "            else:\n",
    "                dp[1][i][0] = dp[1][i - 1][0]\n",
    "                dp[1][i][1] = dp[1][i - 1][1]\n",
    "        for i in range(2 * k, 3 * k):\n",
    "            if presum[i + 1] - presum[i - k + 1] > dp[1][i - 1][0]:\n",
    "                dp[1][i][0] = presum[i + 1] - presum[i - k + 1]\n",
    "                dp[1][i][1] = [i - k + 1, 0, 0]\n",
    "            else:\n",
    "                dp[1][i][0] = dp[1][i - 1][0]\n",
    "                dp[1][i][1] = dp[1][i - 1][1]\n",
    "\n",
    "            if dp[1][i - k][0] + presum[i + 1] - presum[i - k + 1] > dp[2][i - 1][0]:\n",
    "                dp[2][i][0] = dp[1][i - k][0] + presum[i + 1] - presum[i - k + 1]\n",
    "                dp[2][i][1] = [dp[1][i - k][1][0], i - k + 1, 0]\n",
    "            else:\n",
    "                dp[2][i][0] = dp[2][i - 1][0]\n",
    "                dp[2][i][1] = dp[2][i - 1][1]\n",
    "        for i in range(3 * k, n):\n",
    "            if presum[i + 1] - presum[i - k + 1] > dp[1][i - 1][0]:\n",
    "                dp[1][i][0] = presum[i + 1] - presum[i - k + 1]\n",
    "                dp[1][i][1] = [i - k + 1, 0, 0]\n",
    "            else:\n",
    "                dp[1][i][0] = dp[1][i - 1][0]\n",
    "                dp[1][i][1] = dp[1][i - 1][1]\n",
    "\n",
    "            if dp[1][i - k][0] + presum[i + 1] - presum[i - k + 1] > dp[2][i - 1][0]:\n",
    "                dp[2][i][0] = dp[1][i - k][0] + presum[i + 1] - presum[i - k + 1]\n",
    "                dp[2][i][1] = [dp[1][i - k][1][0], i - k + 1, 0]\n",
    "            else:\n",
    "                dp[2][i][0] = dp[2][i - 1][0]\n",
    "                dp[2][i][1] = dp[2][i - 1][1]\n",
    "\n",
    "            if dp[2][i - k][0] + presum[i + 1] - presum[i - k + 1] > dp[3][i - 1][0]:\n",
    "                dp[3][i][0] = dp[2][i - k][0] + presum[i + 1] - presum[i - k + 1]\n",
    "                dp[3][i][1] = [dp[2][i - k][1][0], dp[2][i - k][1][1], i - k + 1]\n",
    "            else:\n",
    "                dp[3][i][0] = dp[3][i - 1][0]\n",
    "                dp[3][i][1] = dp[3][i - 1][1]            \n",
    "        \n",
    "        return dp[3][n - 1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseTable:\n",
    "    def __init__(self, nums, func):\n",
    "        self.func = func\n",
    "        nums = list(nums)\n",
    "        n = len(nums)\n",
    "        self.n = n\n",
    "        self.lg = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            self.lg[i] = self.lg[i // 2] + 1\n",
    "        self.t = [nums] + [[0] * n for _ in range(self.lg[n])]\n",
    "        for i in range(1, self.lg[n] + 1):\n",
    "            step = 1 << i - 1\n",
    "            for j in range(n - step * 2 + 1):\n",
    "                self.t[i][j] = func(self.t[i - 1][j], self.t[i - 1][j + step])\n",
    "\n",
    "    def get(self, l: int, r: int): # left-closed, right-open.\n",
    "        if l >= r or l < 0 or r > self.n:\n",
    "            return -1 # default value\n",
    "        depth = self.lg[r - l]\n",
    "        return self.func(self.t[depth][l], self.t[depth][r - (1 << depth)])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cur = 0\n",
    "        for i in range(k):\n",
    "            cur += nums[i]\n",
    "        ns = [cur]\n",
    "        for i in range(k, n):\n",
    "            cur += nums[i] - nums[i - k]\n",
    "            ns.append(cur)\n",
    "        \n",
    "        st = SparseTable(ns, max)\n",
    "        m = n - k + 1\n",
    "        dp = [(0, []) * 3 for _ in range(m)] # python 2nd array\n",
    "\n",
    "        mv = 0\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            if i > 0:\n",
    "                dp[i] = deepcopy(dp[i - 1])\n",
    "            else:\n",
    "                dp[i] = [(0, []), (0, []), (0, [])]\n",
    "            \n",
    "            if i == 0 or ns[i] > dp[i - 1][0][0]:\n",
    "                dp[i][0] = [ns[i], [i]]\n",
    "\n",
    "            if i >= k:\n",
    "                t = ns[i] + dp[i - k][0][0]\n",
    "                if dp[i][1][0] < t:\n",
    "                    dp[i][1] = (t, dp[i - k][0][1] + [i])\n",
    "            \n",
    "            if i >= 2 * k: \n",
    "                t = ns[i] + dp[i - k][1][0]\n",
    "                if dp[i][2][0] < t:\n",
    "                    dp[i][2] = (t, dp[i - k][1][1] + [i])\n",
    "\n",
    "                    if dp[i][2][0] >= mv:\n",
    "                        mv = dp[i][2][0]\n",
    "                        ans = dp[i][2][1]\n",
    "        \n",
    "        print(dp)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        presum = [0] * (len(nums) + 1)\n",
    "        for i in range(1, len(presum)):\n",
    "            presum[i] = presum[i - 1] + nums[i - 1]\n",
    "\n",
    "        # self.res = []\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        # def dp(i, num):\n",
    "        #     if num == 0:\n",
    "        #         return 0\n",
    "        #     if i + 1 < num * k:\n",
    "        #         return float('-inf')\n",
    "\n",
    "        #     # res = max(dp(i - 1, num), dp(i - k, num - 1) + presum[i + 1] - presum[i - k + 1])\n",
    "\n",
    "        #     res1 = dp(i - 1, num)\n",
    "        #     res2 = dp(i - k, num - 1) + presum[i + 1] - presum[i - k + 1]\n",
    "\n",
    "        #     if res1 >= res2:\n",
    "        #         return res1\n",
    "        #     else:\n",
    "        #         self.res.append(i - k + 1)\n",
    "        #         return res2\n",
    "\n",
    "\n",
    "        dp = [[0] * 4 for _ in range(len(nums) + 1)]\n",
    "\n",
    "        dp[0][1] = float('-inf')\n",
    "        dp[0][2] = float('-inf')\n",
    "        dp[0][3] = float('-inf')\n",
    "\n",
    "        # last = [[0] * 4 for _ in range(len(nums) + 1)]\n",
    "        mp = {}\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                res1 = dp[i - 1][j]\n",
    "                res2 = (dp[i - k][j - 1] + presum[i] - presum[i - k]) if i - k >= 0 else float('-inf')\n",
    "\n",
    "                if res1 >= res2:\n",
    "                    mp[(i, j)] = (i - 1, j)\n",
    "                else:\n",
    "                    mp[(i, j)] = (i - k, j - 1)\n",
    "\n",
    "                dp[i][j] = max(res1, res2)\n",
    "        \n",
    "\n",
    "        ii, jj = len(dp) - 1, len(dp[0]) - 1\n",
    "\n",
    "        cnt = 0\n",
    "        res = []\n",
    "        while cnt < 3:\n",
    "            newi, newj = mp[(ii, jj)]\n",
    "            if newj != jj:\n",
    "                cnt += 1\n",
    "                res.append(newi)\n",
    "                if cnt == 3:\n",
    "                    break\n",
    "            ii, jj = newi, newj\n",
    "\n",
    "        return sorted(res)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = {}\n",
    "        n = len(nums)\n",
    "        tmp = sum(nums[i] for i in range(k))\n",
    "        add = [tmp]\n",
    "        for i in range(k, n):\n",
    "            tmp += nums[i] - nums[i - k]\n",
    "            add.append(tmp)\n",
    "\n",
    "        def helper(idx, num):\n",
    "            if num == 0 or idx + num * k > n:\n",
    "                return 0, []\n",
    "            key = idx, num\n",
    "            value = ans.get(key)\n",
    "            if value is not None:\n",
    "                return value\n",
    "            best, starts = helper(idx + k, num - 1)\n",
    "            best += add[idx]\n",
    "            best1, starts1 = helper(idx + 1, num)\n",
    "            value = (best1, starts1) if best1 > best else (best, [idx] + starts)\n",
    "            ans[key] = value\n",
    "            return value\n",
    "\n",
    "        return helper(0, 3)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ksum = []\n",
    "        tmp = sum(nums[:k])\n",
    "        L = len(nums)\n",
    "        ksum.append(tmp)\n",
    "        for i in range(L-k):\n",
    "            tmp -= nums[i]\n",
    "            tmp += nums[i+k]\n",
    "            ksum.append(tmp)\n",
    "        \n",
    "        ans = [[-1]*(L+1) for _ in range(3)]\n",
    "        def calc(start, remain):\n",
    "            if ans[remain-1][start] != -1:\n",
    "                return ans[remain-1][start]\n",
    "            if remain == 1:\n",
    "                if start == L-k:\n",
    "                    sol = [ksum[start], [-start]]\n",
    "                else:\n",
    "                    sol = max([ksum[start], [-start]], calc(start+1, remain))\n",
    "                ans[remain-1][start] = sol\n",
    "                return sol\n",
    "            if start == L-remain*k:\n",
    "                # sol = calc(start+k, remain-1)+ksum[start]\n",
    "                sol = calc(start+k, remain-1)\n",
    "                sol = [sol[0]+ksum[start], [-start]+sol[1]]\n",
    "                ans[remain-1][start] = sol\n",
    "                return sol\n",
    "\n",
    "            sol1 = calc(start+1, remain)\n",
    "            # sol2 = calc(start+k, remain-1)+ksum[start]\n",
    "            sol2 = calc(start+k, remain-1)\n",
    "            sol2 = [sol2[0]+ksum[start], [-start]+sol2[1]]\n",
    "            ans[remain-1][start] = max(sol2, sol1)\n",
    "            return ans[remain-1][start]\n",
    "        sol = calc(0, 3)\n",
    "        return [-x for x in sol[1]]\n",
    "\n",
    "# print(Solution().maxSumOfThreeSubarrays(nums = [1,2,1,2,6,7,5,1], k = 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        self.k = k\n",
    "        self.n = len(nums)\n",
    "        self.nums = nums\n",
    "        self.sum = [0 for _ in self.nums]\n",
    "        self.sum[0] = nums[0]\n",
    "        self.memo = dict()\n",
    "        for i in range(1, self.n):\n",
    "            self.sum[i] = self.sum[i - 1] + self.nums[i]\n",
    "        res = self.dfs(0, 3)\n",
    "        res[1].reverse()\n",
    "        return res[1]\n",
    "\n",
    "    def dfs(self, i, j):\n",
    "        if self.n - i < self.k * j:  # 剩下的元素已经无法满足条件了\n",
    "            return [-9999999, []]\n",
    "        if j == 0:  # 已经选完了\n",
    "            return [0, []]  # 设置为零不能影响结果\n",
    "        if (i, j) in self.memo:\n",
    "            return self.memo.get((i, j))\n",
    "\n",
    "        a = self.dfs(i + 1, j)  # 不选\n",
    "        b = self.dfs(i + self.k, j - 1)  # 选\n",
    "        res = [0, []]\n",
    "        if a[0] > b[0] + self.sum[i + self.k - 1] - self.sum[i] + self.nums[i]:\n",
    "            res = a\n",
    "        else:\n",
    "            temp = b[1].copy()\n",
    "            temp.append(i)\n",
    "            res = (b[0] + self.sum[i + self.k - 1] - self.sum[i] + self.nums[i], temp)\n",
    "        self.memo[(i, j)] = res  # 将 self.memo 更新移到这里\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ls = len(nums) - k + 1\n",
    "        # memo[i] = nums[i:i+k]的和\n",
    "        memo = [sum(nums[i:i+k])for i in range(ls)]\n",
    "\n",
    "        # dp[choice_num][i] = [indexes, sum]\n",
    "        # [i:]选择choice_num个数，ans为indexes，和为sum\n",
    "        dp = [[[set(), float('-inf')] for i in range(ls+1)] for num in range(0, 4)]\n",
    "\n",
    "        # dp[1]\n",
    "        for i in range(ls-1, -1, -1):\n",
    "            # 选择i子数组\n",
    "            su = memo[i]\n",
    "            dp[1][i][0].add(i)\n",
    "            dp[1][i][1] = su\n",
    "            # 不选i子数组\n",
    "            su_r = dp[1][i+1][1]\n",
    "            if su < su_r:\n",
    "                dp[1][i] = dp[1][i+1]\n",
    "        \n",
    "        # dp[2]\n",
    "        for i in range(ls-1-k, -1, -1):\n",
    "            su = memo[i] + dp[1][i+k][1]\n",
    "            dp[2][i][0] = dp[1][i+k][0].union([i])\n",
    "            dp[2][i][1] = su\n",
    "            su_r = dp[2][i+1][1]\n",
    "            if su < su_r:\n",
    "                dp[2][i] = dp[2][i+1]\n",
    "\n",
    "        # dp[2]\n",
    "        for i in range(ls-1-k-k, -1, -1):\n",
    "            su = memo[i] + dp[2][i+k][1]\n",
    "            dp[3][i][0] = dp[2][i+k][0].union([i])\n",
    "            dp[3][i][1] = su\n",
    "            su_r = dp[3][i+1][1]\n",
    "            if su < su_r:\n",
    "                dp[3][i] = dp[3][i+1]\n",
    "            \n",
    "        return list(sorted(dp[3][0][0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sum(self, l, r):\n",
    "        return self.lsum[r+1] - self.lsum[l]\n",
    "\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        f, self.len = {}, k\n",
    "        sum_v, self.lsum = 0, [0]\n",
    "        for num in nums:\n",
    "            sum_v += num\n",
    "            self.lsum.append(sum_v)\n",
    "        \n",
    "        prev, maxi_state = {}, (0, 0)\n",
    "        f[(-1, 0)] = 0\n",
    "        prev[(-1, 0)] = None\n",
    "        for i in range(len(nums)):\n",
    "            f[(i, 0)] = 0\n",
    "            prev[(i, 0)] = None\n",
    "            for k in range(1, 4):\n",
    "                f[(i, k)] = 0 if i == 0 else f[(i-1, k)]\n",
    "                prev[(i, k)] = None if i == 0 else (i-1, k)\n",
    "                if i+1 < k * self.len:\n",
    "                    continue\n",
    "                new_ans = f[(i-self.len, k-1)] + self.sum(i-self.len+1, i)\n",
    "                if new_ans > f[(i, k)]:\n",
    "                    f[(i, k)] = new_ans\n",
    "                    prev[(i, k)] = (i-self.len, k-1)\n",
    "                if f[(i, k)] > f[maxi_state]:\n",
    "                    maxi_state = (i, k)\n",
    "        # print(f'maxi state is {maxi_state} with value {f[maxi_state]}')\n",
    "        \n",
    "        cur_state, ans = maxi_state, []\n",
    "        while prev[cur_state]:\n",
    "            # print(f'cur_state = {cur_state}, prev_state = {prev[cur_state]}')\n",
    "            if prev[cur_state][1] != cur_state[1]:\n",
    "                ans.append(cur_state[0] - self.len + 1)\n",
    "            cur_state = prev[cur_state]\n",
    "        ans.reverse()\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        acc = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            acc[i] = acc[i - 1] + nums[i]\n",
    "\n",
    "        def merge(t1, t2):\n",
    "            return t1[0] + t2[0], t1[1] + t2[1]\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            if m == 0:\n",
    "                return 0, []\n",
    "            if n - i < m * k:\n",
    "                return 0, []\n",
    "            ans_1 = dp(i + 1, m)\n",
    "            ans_2 = merge((acc[i+k-1] - acc[i-1], [i]), dp(i + k, m - 1))\n",
    "\n",
    "            if ans_1[0] > ans_2[0]:\n",
    "                return ans_1\n",
    "            return ans_2\n",
    "        return dp(0, 3)[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        acc = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            acc[i] = acc[i - 1] + nums[i]\n",
    "\n",
    "        def merge(t1, t2):\n",
    "            return t1[0] + t2[0], t1[1] + t2[1]\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            if m == 0:\n",
    "                return 0, []\n",
    "\n",
    "            if n - i < m * k:\n",
    "                return 0, []\n",
    "\n",
    "            res_1 = dp(i + 1, m)\n",
    "            res_2 = merge((acc[i + k - 1] - acc[i - 1], [i]), dp(i + k, m - 1))\n",
    "\n",
    "            if res_1[0] > res_2[0]:\n",
    "                return res_1\n",
    "            return res_2\n",
    "\n",
    "        return dp(0, 3)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxSumOfThreeSubarrays(self, nums, k: int):\r\n",
    "        k_sums = []\r\n",
    "        for i in range(len(nums) - k + 1):\r\n",
    "            k_sums.append(sum(nums[i: i+k]))\r\n",
    "        results = []\r\n",
    "        best_results = []\r\n",
    "        max_sum = -float('inf')\r\n",
    "        # def dfs(index):\r\n",
    "        #     nonlocal k_sums\r\n",
    "        #     nonlocal results\r\n",
    "        #     nonlocal best_results\r\n",
    "        #     nonlocal max_sum\r\n",
    "        #     if len(results) == 3:\r\n",
    "        #         if k_sums[results[0]] + k_sums[results[1]]+ k_sums[results[2]] > max_sum:\r\n",
    "        #             max_sum = k_sums[results[0]] + k_sums[results[1]]+ k_sums[results[2]]\r\n",
    "        #             best_results = results[:]\r\n",
    "        #             return\r\n",
    "        #         else:\r\n",
    "        #             return\r\n",
    "        #     if index >= len(k_sums):\r\n",
    "        #         return \r\n",
    "        #     for i in range(index, len(k_sums)):\r\n",
    "        #         results.append(i)\r\n",
    "        #         dfs(i+k)\r\n",
    "        #         results.pop(-1)\r\n",
    "        # dfs(0)\r\n",
    "        tag = {}\r\n",
    "        result = self.step_sum(k_sums, k, 0, tag, 0)\r\n",
    "        return result[1]\r\n",
    "    def step_sum(self, nums, k, index, tag, count):\r\n",
    "        if count == 3:\r\n",
    "            return 0, []\r\n",
    "        if index >= len(nums):\r\n",
    "            return 0, []\r\n",
    "        if (index, count) in tag:\r\n",
    "            return tag[(index, count)]\r\n",
    "        csum, clist = self.step_sum(nums, k, index+k, tag, count+1)\r\n",
    "        csum += nums[index]\r\n",
    "        clist = [index] + clist\r\n",
    "        nsum, nlist = self.step_sum(nums, k, index+1, tag, count)\r\n",
    "        if csum >= nsum:\r\n",
    "            tag[(index, count)] = (csum, clist)\r\n",
    "            return tag[(index, count)]\r\n",
    "        else:\r\n",
    "            tag[(index, count)] = (nsum, nlist)\r\n",
    "            return tag[(index, count)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = {}\n",
    "        n = len(nums)\n",
    "        tmp = sum(nums[i] for i in range(k))\n",
    "        add = [tmp]\n",
    "        for i in range(k, n):\n",
    "            tmp += nums[i] - nums[i - k]\n",
    "            add.append(tmp)\n",
    "\n",
    "        def helper(idx, num):\n",
    "            if num == 0 or idx + num * k > n:\n",
    "                return 0, []\n",
    "            key = idx, num\n",
    "            value = ans.get(key)\n",
    "            if value is not None:\n",
    "                return value\n",
    "            best, starts = helper(idx + k, num - 1)\n",
    "            best += add[idx]\n",
    "            best1, starts1 = helper(idx + 1, num)\n",
    "            value = (best1, starts1) if best1 > best else (best, [idx] + starts)\n",
    "            ans[key] = value\n",
    "            return value\n",
    "\n",
    "        return helper(0, 3)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # try all middle subarrays.\n",
    "    # dp on left and right max sums\n",
    "    # O(n) time and space\n",
    "\n",
    "    # TODO: try generic solution!!! X NON OVER LAPPING SUBARRAYS\n",
    "    # USE dp(i, X): just take a subarray of size k, then recurse on dp(j+1, X-1)\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        prefix_sums = list(accumulate(nums)) + [0]\n",
    "        @cache\n",
    "        def window_sum(i):\n",
    "            # if i < 0: return 0\n",
    "            # if i + k > n: return 0\n",
    "            return prefix_sums[i+k-1] - prefix_sums[i-1]\n",
    "            #return nums[i:i+k]\n",
    "        \n",
    "        #nums.append(inf)\n",
    "\n",
    "        # acceptable range: i in [k-1, n-1]\n",
    "        # i is the ENDING INDEX\n",
    "        @cache\n",
    "        def leftPrefix(i): # return min STARTING index of max sum from nums[:i+1]\n",
    "            #if i < k-1: return -1\n",
    "            if i == k-1: return 0 # STARTING INDEX\n",
    "            if window_sum(leftPrefix(i-1)) >= window_sum(i-k+1):\n",
    "                return leftPrefix(i-1)\n",
    "            else:\n",
    "                return i-(k-1)\n",
    "                #return i # STARTING INDEX;;; NOT i\n",
    "        \n",
    "        # acceptable range: i in [0, n-k]\n",
    "        @cache\n",
    "        def rightPrefix(i): # return min index of max sum from nums[i:]\n",
    "            if i == n-k: return n-k\n",
    "\n",
    "            if window_sum(i) >= window_sum(rightPrefix(i+1)):\n",
    "                return i\n",
    "            else:\n",
    "                return rightPrefix(i+1)\n",
    "        \n",
    "        max_sum = 0\n",
    "        res = []\n",
    "\n",
    "        # try all starting points for the middle segment\n",
    "        for i in range(k, n-2*k + 1):\n",
    "            left_ending = i-1\n",
    "            right_starting = i+k\n",
    "\n",
    "            l = leftPrefix(left_ending) # max sum starting l index\n",
    "            r = rightPrefix(right_starting) # max sum starting r index\n",
    "\n",
    "            triple_sum = window_sum(l) + window_sum(i) + window_sum(r)\n",
    "\n",
    "            if triple_sum > max_sum: # note: >= would mess up the lexico smallest\n",
    "                max_sum = triple_sum\n",
    "                res = [l, i, r]\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# C++/Java, DP with explanation, O(n)\n",
    "# zestypanda\n",
    "# 4049\n",
    "# 47118\n",
    "# Sep 30, 2017\n",
    "# The question asks for three non-overlapping intervals with maximum sum of all 3 intervals. If the middle interval is [i, i+k-1], where k <= i <= n-2k, the left interval has to be in subrange [0, i-1], and the right interval is from subrange [i+k, n-1].\n",
    "\n",
    "# So the following solution is based on DP.\n",
    "\n",
    "# posLeft[i] is the starting index for the left interval in range [0, i];\n",
    "# posRight[i] is the starting index for the right interval in range [i, n-1]; \n",
    "# Then we test every possible starting index of middle interval, i.e. k <= i <= n-2k, and we can get the corresponding left and right max sum intervals easily from DP. And the run time is O(n).\n",
    "\n",
    "# Caution. In order to get lexicographical smallest order, when there are two intervals with equal max sum, always select the left most one. So in the code, the if condition is \">= tot\" for right interval due to backward searching, and \"> tot\" for left interval. Thanks to @lee215 for pointing this out!\n",
    "\n",
    "# class Solution {\n",
    "# public:\n",
    "#     vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {\n",
    "#         int n = nums.size(), maxsum = 0;\n",
    "#         vector<int> sum = {0}, posLeft(n, 0), posRight(n, n-k), ans(3, 0);\n",
    "#         for (int i:nums) sum.push_back(sum.back()+i);\n",
    "#        // DP for starting index of the left max sum interval\n",
    "#         for (int i = k, tot = sum[k]-sum[0]; i < n; i++) {\n",
    "#             if (sum[i+1]-sum[i+1-k] > tot) {\n",
    "#                 posLeft[i] = i+1-k;\n",
    "#                 tot = sum[i+1]-sum[i+1-k];\n",
    "#             }\n",
    "#             else \n",
    "#                 posLeft[i] = posLeft[i-1];\n",
    "#         }\n",
    "#         // DP for starting index of the right max sum interval\n",
    "#         // caution: the condition is \">= tot\" for right interval, and \"> tot\" for left interval\n",
    "#         for (int i = n-k-1, tot = sum[n]-sum[n-k]; i >= 0; i--) {\n",
    "#             if (sum[i+k]-sum[i] >= tot) {\n",
    "#                 posRight[i] = i;\n",
    "#                 tot = sum[i+k]-sum[i];\n",
    "#             }\n",
    "#             else\n",
    "#                 posRight[i] = posRight[i+1];\n",
    "#         }\n",
    "#         // test all possible middle interval\n",
    "#         for (int i = k; i <= n-2*k; i++) {\n",
    "#             int l = posLeft[i-1], r = posRight[i+k];\n",
    "#             int tot = (sum[i+k]-sum[i]) + (sum[l+k]-sum[l]) + (sum[r+k]-sum[r]);\n",
    "#             if (tot > maxsum) {\n",
    "#                 maxsum = tot;\n",
    "#                 ans = {l, i, r};\n",
    "#             }\n",
    "#         }\n",
    "#         return ans;\n",
    "#     }\n",
    "# };"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = {}\n",
    "        n = len(nums)\n",
    "        tmp = sum(nums[i] for i in range(k))\n",
    "        add = [tmp]\n",
    "        for i in range(k, n):\n",
    "            tmp += nums[i] - nums[i - k]\n",
    "            add.append(tmp)\n",
    "\n",
    "        def helper(idx, num):\n",
    "            if num == 0 or idx + num * k > n:\n",
    "                return 0, []\n",
    "            key = idx, num\n",
    "            value = ans.get(key)\n",
    "            if value is not None:\n",
    "                return value\n",
    "            best, starts = helper(idx + k, num - 1)\n",
    "            best += add[idx]\n",
    "            best1, starts1 = helper(idx + 1, num)\n",
    "            value = (best1, starts1) if best1 > best else (best, [idx] + starts)\n",
    "            ans[key] = value\n",
    "            return value\n",
    "\n",
    "        return helper(0, 3)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        p=[0]\n",
    "        for num in nums:p.append(p[-1]+num)\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(left,d):\n",
    "            if n-left<d*k:return float('-inf'),[]\n",
    "            if d==0:return 0,[]\n",
    "            s1,li1=dp(left+k,d-1)\n",
    "            s,li=s1+p[left+k]-p[left],[left]+li1\n",
    "            s2,li2=dp(left+1,d)\n",
    "            if s2>s:s,li=s2,li2\n",
    "            return s,li \n",
    "        \n",
    "        return dp(0,3)[1]\n",
    "            \n",
    "            \n",
    "           \n",
    "            \n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:   \n",
    "        def dfs(idx, time):\n",
    "            if idx + k > numlen:\n",
    "                return (-math.inf, [])\n",
    "            if dp[idx][time] == None:\n",
    "                if time == 0:\n",
    "                    beforemax, beforemaxlist = dfs(idx + 1, time)\n",
    "                    if sum(nums[idx:idx + k]) >= beforemax:\n",
    "                        dp[idx][time] = (sum(nums[idx:idx + k]), [idx])\n",
    "                    else:\n",
    "                        dp[idx][time] = dfs(idx + 1, time)\n",
    "                else:\n",
    "                    choosed, choosedlist = dfs(idx + k, time - 1)\n",
    "                    newchoosed = choosed + sum(nums[idx:idx + k])\n",
    "                    nochoosed, nochoosedlist = dfs(idx + 1, time)\n",
    "                    if newchoosed >= nochoosed:\n",
    "                        dp[idx][time] = (newchoosed, [idx] + choosedlist)\n",
    "                    else:\n",
    "                        dp[idx][time] = dfs(idx + 1, time)\n",
    "            return dp[idx][time]\n",
    "                \n",
    "        numlen = len(nums)\n",
    "        dp = [[None for i in range(3)] for j in range(numlen)]\n",
    "        return dfs(0, 2)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums, k: int):\n",
    "        n = len(nums)\n",
    "        dp = [[[0, [n-1]*3] for _ in range(n)] for _ in range(3)]\n",
    "\n",
    "        def find_sub(i, m):\n",
    "            if i + m * k > n:\n",
    "                return 0, None\n",
    "            if dp[m - 1][i][0]:\n",
    "                return dp[m - 1][i][0], dp[m-1][i][1]\n",
    "\n",
    "            if m == 1:\n",
    "                a = sum(nums[i:i + k])\n",
    "                pa = dp[m-1][i][1]\n",
    "                b, pb = find_sub(i + 1, 1)\n",
    "            else:\n",
    "                a, pa = find_sub(i + k, m - 1)\n",
    "                a += sum(nums[i:i + k])\n",
    "                b, pb = find_sub(i + 1, m)\n",
    "\n",
    "            if a >= b:\n",
    "                dp[m - 1][i][0] = a\n",
    "                dp[m - 1][i][1] = pa.copy()\n",
    "                dp[m - 1][i][1][3-m] = i\n",
    "            else:\n",
    "                dp[m - 1][i][0] = b\n",
    "                dp[m - 1][i][1] = pb.copy()\n",
    "\n",
    "            return dp[m - 1][i][0], dp[m - 1][i][1]\n",
    "\n",
    "        _, p = find_sub(0, 3)\n",
    "        return p\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # 前缀和\n",
    "        pre = [0] \n",
    "        for num in nums:\n",
    "            pre.append(pre[-1] + num)\n",
    "        # 对应(i, j) 存的下标\n",
    "        c = defaultdict(set)\n",
    "        # f[i][j] 到当前i为止，选了j个时的最大值。\n",
    "        f = [[float('-inf')] * 4 for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            f[i][0] = 0\n",
    "\n",
    "        for i in range(k, n + 1):\n",
    "            num = pre[i] - pre[i-k]\n",
    "            for j in range(1, 4):\n",
    "                # 不选当前i\n",
    "                f[i][j] = f[i-1][j]\n",
    "                c[(i, j)] = c[(i - 1, j)]\n",
    "                # 选当前i\n",
    "                if f[i-k][j-1] + num > f[i][j]:\n",
    "                    f[i][j] = f[i-k][j-1] + num\n",
    "                    c[(i, j)] = c[(i-k, j-1)] | set([i-k])\n",
    "              \n",
    "            \n",
    "        return sorted(c[(n, 3)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(indx,t):\n",
    "            if t == 0:\n",
    "                return (0,[])\n",
    "            if n-indx < t*k:\n",
    "                return (-inf,[])\n",
    "            if indx == n and t == 0:\n",
    "                return (0,[])\n",
    "            s1,a1 = f(indx+1, t)\n",
    "            s2,a2 = f(indx+k, t-1)\n",
    "            a = [indx]\n",
    "            a.extend(a2)\n",
    "            if s2+sum(nums[indx:indx+k]) >= s1:\n",
    "                res = (s2+sum(nums[indx:indx+k]), a)\n",
    "            else:\n",
    "                res = (s1, a1)\n",
    "            return res\n",
    "        return f(0,3)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        preSum = [0] + list(accumulate(nums))\n",
    "\n",
    "        @cache\n",
    "        def f(i, t):\n",
    "            if t == 1:\n",
    "                if i == k - 1:\n",
    "                    return preSum[i + 1], [0]\n",
    "                else:\n",
    "                    s, ids = f(i - 1, t)\n",
    "                    curS = preSum[i + 1] - preSum[i + 1 - k]\n",
    "                    if curS > s:\n",
    "                        return curS, [i + 1 - k]\n",
    "                    else:\n",
    "                        return s, ids\n",
    "            else:\n",
    "                if i == t * k - 1:\n",
    "                    s, ids = f(i - k, t - 1)\n",
    "                    curS = preSum[i + 1] - preSum[i + 1 - k]\n",
    "                    return s + curS, ids + [i + 1 - k]\n",
    "                else:\n",
    "                    s, ids = f(i - 1, t)\n",
    "                    curS = preSum[i + 1] - preSum[i + 1 - k]\n",
    "                    ps, pids = f(i - k, t - 1)\n",
    "                    if curS + ps > s:\n",
    "                        return ps + curS, pids + [i + 1 - k]\n",
    "                    else:\n",
    "                        return s, ids\n",
    "\n",
    "        return f(n - 1, 3)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, left):\n",
    "            if i + left * k > n: return -inf, []\n",
    "            if left == 0: return 0, []\n",
    "\n",
    "            suma, lsta = dfs(i+1, left)\n",
    "            sumb, lstb = dfs(i+k, left-1)\n",
    "\n",
    "            if sumb + pre[i+k] - pre[i] >= suma: return sumb + pre[i+k] - pre[i], [i] + lstb\n",
    "            else: return suma, lsta\n",
    "        return dfs(0, 3)[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
